/// @tags:
#include <cstdio>
#include <cstring>
#include <iostream>
#define rint register int

using std::cin;
using std::cout;

namespace BlueQuantum {

typedef long long LL;

constexpr int maxn = 1.5e5 + 3, blksiz = 750, S = (1 << 19) - 1,
              maxm = maxn > blksiz *blksiz * 2 ? maxn : blksiz *blksiz * 2;

int n, m, q, tot, buk[maxn];
int a[maxn], opt[maxn], L[maxn], R[maxn], w[maxn];
LL ans[maxn], sum[blksiz * 2];

struct Node {
  int x, y;
} b[maxn], tb[maxn], c[maxm], tc[maxm];

inline void clear(int *begin, int *end) { memset(begin, 0, (end - begin) << 2); }

inline void sort(const Node a[], int len, Node res[]) {
  clear(buk, buk + m + 1);
  for (int i = 1; i <= len; ++i) buk[a[i].x]++;
  for (int i = 1; i <= m; ++i) buk[i] += buk[i - 1];
  for (int i = len; i >= 1; --i) res[buk[a[i].x]--] = a[i];
}

inline void solve() {
  static int id[maxn], buk[blksiz << 1], len[blksiz << 1], bl[blksiz << 1], br[blksiz << 1];
  for (int l = 1, r; l <= q; l = r + 1) {
    r = std::min(l + blksiz - 2, q);
    clear(id + 1, id + 1 + n);
    int lst = 0, cur = 0;
    id[1] = 1, tot = 0;
    for (int i = l; i <= r; ++i) id[L[i]] = id[R[i] + 1] = 1;
    for (int i = 1; i <= n; ++i) b[i] = Node{a[i], id[i] += id[i - 1]};
    for (int i = 1; i <= n; ++i)
      if ((cur = id[i]) != id[i + 1]) len[cur] = i - lst, bl[cur] = lst + 1, br[cur] = lst = i;
    for (int i = 1; i <= id[n]; ++i) {
      sum[i] = 0;
      int dl = bl[i], dr = br[i], tmp = 0;
      for (int j = l; j <= r; ++j)
        if (L[j] <= dl && dr <= R[j]) {
          if (opt[j] == 1) {
            if ((tmp += w[j]) >= m) tmp -= m;
          } else
            c[++tot] = Node{m - tmp, i << 20 | j};
        }
      for (int j = dl; j <= dr; ++j) {
        sum[i] += a[j];
        if ((a[j] += tmp) >= m) a[j] -= m;
      }
    }
    sort(b, n, tb);
    sort(c, tot, tc);
    int bcnt = n, ccnt = tot, bid, pos;
    Node *i = tb + 1, *j = tc + 1;
    while (bcnt && ccnt)
      if (i->x < j->x)
        buk[i++->y]++, bcnt--;
      else {
        pos = j->y & S, bid = j->y >> 20;
        ccnt--;
        ans[pos] += sum[bid] + LL(m - j++->x) % m * len[bid] - LL(len[bid] - buk[bid]) * m;
      }
    while (ccnt--) bid = j->y >> 20, ans[j->y & S] += sum[bid] + LL(m - j->x) % m * len[bid], j++;
    tot = id[n];
    clear(len + 1, len + 1 + tot);
    clear(buk + 1, buk + 1 + tot);
  }
}

inline int main() {
  cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= q; ++i) {
    cin >> opt[i] >> L[i] >> R[i];
    if (opt[i] == 1) cin >> w[i];
  }
  solve();
  for (int i = 1; i <= q; ++i)
    if (opt[i] == 2) cout << ans[i] << '\n';
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("sequence.in", "r", stdin);
  freopen("sequence.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
